package com.algorithm2;

import java.util.Arrays;

public class HeapSort4 {

    public static void heapSort(int[] array){
        buildHeap(array,array.length-1);
        System.out.println("构建buildHeap完:" + Arrays.toString(array));
        int len = array.length-1;
        for(int i=len;i>=1;i--){
            swap(array,i,1);
            System.out.println(i+"-->交换完数据:"+Arrays.toString(array));
            len--;
            heapify(array,len,1);

        }
        System.out.println("堆排结果:" + Arrays.toString(array));

    }
    public static void buildHeap(int[] array,int len){
        for(int i = len/2;i>=1;i--){
            heapify(array,len,i);
        }
    }

    public static void heapify(int[] array,int len,int k){
        int maxP = k;
        int left = 2*k;
        int right = 2*k+1;
        if(left<len && array[maxP]<array[left])
            maxP = left;
        if(right<len && array[maxP]<array[right])
            maxP = right;
        if(maxP!=k){
            swap(array,k,maxP);
            heapify(array,len,maxP);
            System.out.println("k为："+"-->"+k +"-->"+ Arrays.toString(array));
        }


    }

    public static void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args){
        int[] array = new int[]{0,8, 9, 3,10, 2, 4, 5, 6, 7, 1};
        //buildHeap(array,array.length-1);
        //System.out.println("构建堆:" + Arrays.toString(array));
        heapSort(array);



    }
}
